package geekstudy.week6;

import java.util.Arrays;

/**
 *
 * 279. 完全平方数
 * https://leetcode-cn.com/problems/perfect-squares/submissions/
 *
 * 执行结果： 通过 显示详情
 *
 * 添加备注
 * 执行用时：26 ms, 在所有 Java 提交中击败了89.78% 的用户
 * 内存消耗：37.4 MB, 在所有 Java 提交中击败了72.75% 的用户
 *
 *
 */
public class Week6PerfectSquares {

    public int numSquares(int n) {
        int square = (int)Math.sqrt(n); // 得到n的开方

        // dynamicPlanning[i] 表示对于正整数i，组成和的完全平方数的最少个数为dp[i]
        int[] dynamicPlanning = new int[n + 1];

        Arrays.fill(dynamicPlanning, n + 1);
        dynamicPlanning[0] = 0;
        dynamicPlanning[1] = 1;
        for(int max = 0; max <= square; max++){

            int temp = max * max;
            for(int detect = temp; detect <= n; detect++){
                dynamicPlanning[detect] = Math.min(dynamicPlanning[detect], dynamicPlanning[detect - temp] + 1);
            }
        }
        return dynamicPlanning[n];
    }
}
